NC17 最长回文子串

https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

暴力法：

func getLongestPalindrome( str string ) int {
    max := 0

    for i := 0; i < len(str); i++ {
        for j := i; j < len(str); j++ {
            if isRome(str[i:j + 1]) {
                max = Max(max, j - i + 1)
            }
        }
    }

    return max
}

func Max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func isRome(str string) bool {
    i, j := 0, len(str) - 1
    for i < j {
        if str[i] != str[j] {
            return false
        }
        i++
        j--
    }
    return true
}

时间复杂度：O(n^3)

动态规划：

func getLongestPalindrome(str string) int {
    length := len(str)

    dp := make([][]bool, length) // 创建二维数组
    for i := 0; i < length; i++ {
        dp[i] = make([]bool, length)
    }

    for i := 0; i < length; i++ {
        dp[i][i] = true
    }

    max := 1

    for j := 1; j < length; j++ {
        // 只取半边
        for i := 0; i < length-1 && i < j; i++ {
            if str[i] != str[j] {
                dp[i][j] = false
            } else {
                if j-i < 3 {
                    dp[i][j] = true
                } else {
                    // 状态递推公式
                    dp[i][j] = dp[i+1][j-1]
                }
            }

            if dp[i][j] == true && j-i+1 > max {
                max = Max(max, j - i + 1)
            }
        }
    }

    return max
}

func Max(a, b int) int {
    if a > b {
        return a
    }

    return b
}